// The nuts and bolts problem, to understand quicksort better.
// Our assumption is that we cannot compare nuts to nuts, bolts to bolts,
// but we can try to match nuts to bolts

#include <assert.h>
#include <iostream>
#include <iterator>
#include <vector>



struct Nut
{
  Nut(std::size_t s)
    : size(s)
  { }

  std::size_t size;
};


std::ostream&
operator<< (std::ostream& os, const Nut n)
{
  return os << n.size;
}



struct Bolt
{
  Bolt(std::size_t s)
    : size(s)
  { }

  std::size_t size;
};



std::ostream&
operator<< (std::ostream& os, const Bolt b)
{
  return os << b.size;
}

typedef std::vector<Nut> NutVec;
typedef std::vector<Bolt> BoltVec;



void
gen_data(const std::size_t n, NutVec& nuts, BoltVec& bolts)
{
  srand ( time(NULL) );
  for (std::size_t i = 0; i < n; ++i)
    {
      std::size_t j = rand() % 20;
      nuts.push_back(Nut(j));
    }

  std::vector<bool> marked(n, false);

  for (std::size_t i = 0; i < n; ++i)
    {
      std::size_t j = rand() % n;
      while (marked[j])
	{
	  j = rand() % n;
	}
      marked[j] = true;
      bolts.push_back(Bolt(nuts[j].size));
    }
}



void
swap(NutVec::iterator it, NutVec::iterator jt)
{
  std::size_t tmp = it->size;
  it->size = jt->size;
  jt->size = tmp;
}




void
partition(NutVec& nuts, NutVec::iterator low, NutVec::iterator high, std::size_t val,
	  NutVec::iterator& min_it, NutVec::iterator& eq_it)
{
  min_it = low;

  for (NutVec::iterator it = low; it != high; ++it)
    {
      if (it->size < val)
	{
	  swap(it, min_it);
	  min_it++;
	}
    }
  eq_it = min_it;
  
  
  for (NutVec::iterator it = eq_it; it != high; ++it)
    {
      if (it->size == val)
	{
	  swap(it, eq_it);
	  eq_it++;
	}
    }
  eq_it--;
}


void
swap(BoltVec::iterator it, BoltVec::iterator jt)
{
  std::size_t tmp = it->size;
  it->size = jt->size;
  jt->size = tmp;
}




void
partition(BoltVec& bolts, BoltVec::iterator low, BoltVec::iterator high, std::size_t val,
	  BoltVec::iterator& min_it, BoltVec::iterator& eq_it)
{
  min_it = low;

  for (BoltVec::iterator it = low; it != high; ++it)
    {
      if (it->size < val)
	{
	  swap(it, min_it);
	  min_it++;
	}
    }

  eq_it = min_it;
  
  for (BoltVec::iterator it = eq_it; it != high; ++it)
    {
      if (it->size == val)
	{
	  swap(it, eq_it);
	  eq_it++;
	}
    }
  eq_it--;
}



void
match(NutVec& nuts, BoltVec& bolts, 
      NutVec::iterator  n_low, NutVec::iterator  n_high,
      BoltVec::iterator b_low, BoltVec::iterator b_high)
{
  if (n_low == n_high)
    {
      assert (b_low == b_high);
    }
  else
    {
      BoltVec::iterator pivot = b_high;
      pivot--;
      std::size_t bolt_size = pivot->size;

      NutVec::iterator n_min_it;
      NutVec::iterator n_eq_it;

      partition(nuts, n_low, n_high, bolt_size, n_min_it, n_eq_it);

      BoltVec::iterator b_min_it;
      BoltVec::iterator b_eq_it;
      partition(bolts, b_low, b_high, n_eq_it->size, b_min_it, b_eq_it);
 
      if (n_min_it != n_low)
	{
	  match(nuts, bolts, n_low, n_min_it, b_low, b_min_it);
	}

      assert (n_eq_it->size == b_eq_it->size);

      n_eq_it++;
      b_eq_it++;
      match(nuts, bolts, n_eq_it, n_high, b_eq_it, b_high);
    }
}



int
main(int argc, char* argv[])
{
  std::size_t n;
  if (argc == 1)
    {
      n = 10;
    }
  else
    {
      n = (std::size_t)std::atoi(argv[1]);
    }

  NutVec nuts;
  BoltVec bolts;
  gen_data(n, nuts, bolts);

  std::copy(nuts.begin(), nuts.end(), std::ostream_iterator<Nut>(std::cout, " "));
  std::cout << std::endl;
  std::copy(bolts.begin(), bolts.end(), std::ostream_iterator<Bolt>(std::cout, " "));
  std::cout << std::endl;

  match(nuts, bolts, nuts.begin(), nuts.end(), bolts.begin(), bolts.end());

  std::copy(nuts.begin(), nuts.end(), std::ostream_iterator<Nut>(std::cout, " "));
  std::cout << std::endl;
  std::copy(bolts.begin(), bolts.end(), std::ostream_iterator<Bolt>(std::cout, " "));
  std::cout << std::endl;
}
